import java.util.Arrays;

public class Solution56 {
    public static void main(String[] args) {
        int[][] intervals = {{3,4},{5,6},{7,8},{1,9},{10,12}};
        int[][] result = merge(intervals);
        for (int i = 0; i < result.length; i++) {
            System.out.println(Arrays.toString(result[i]));
        }
    }

    public static int[][] merge(int[][] intervals) {

        //先将intervals排序
        quickSort(intervals);
        int right = 0;
        //需要一个指针用来指向全新的输出数组
        int index=0;
        int[][] mergedIntervals = new int[intervals.length][2];
        while (right < intervals.length-1){
            if(canBeMerged(intervals[right],intervals[right+1])){
                intervals[right+1] = mergeTwo(intervals[right],intervals[right+1]);
                right++;
                continue;
            }
            mergedIntervals[index++] = intervals[right];
            right++;
        }
        mergedIntervals[index] = intervals[right];
        int[][] rs = new int[index+1][2];
        System.arraycopy(mergedIntervals, 0, rs, 0, index + 1);
        return rs;
    }

    public static int[] mergeTwo(int[] arr1, int[] arr2){
        int[] rs = new int[2];
        rs[0]=Math.min(arr1[0],arr2[0]);
        rs[1]=Math.max(arr1[1],arr2[1]);
        return rs;
    }
    /**
     * 判断两个区间能否合并
     * @param arr1 区间1
     * @param arr2 区间2
     * @return true为能合并，false为不能合并
     */
    public static boolean canBeMerged(int[] arr1, int[] arr2){
        return (arr1[0]==arr2[0]) || (arr1[1]>=arr2[0]) || (arr1[1]>=arr2[1]);
    }

    /**
     * 排序二维数组，使用插入排序的方法
     * @param arr 要排序的二维数组
     */
    public static void sort(int[][] arr){
        //假定第0个元素为最小，从第1个元素开始
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j >=1 ; j--) {
                if(less(arr[j],arr[j-1])){
                    exch(arr,j,j-1);
                }
            }
        }
    }

    /**
     * 使用快速排序
     * @param arr 待排序数组
     */
    public static void quickSort(int[][] arr){
        int left = 0;
        int right = arr.length-1;
        quickSort(arr,left,right);
    }

    /**
     *
     * @param arr 待排序数组
     * @param lo 左边界
     * @param hi 又边界
     */
    public static void quickSort(int[][] arr, int lo, int hi){
        if (lo>=hi){
            return;
        }
        int mid = partition(arr, lo, hi);
        quickSort(arr,lo,mid-1);
        quickSort(arr,mid+1,hi);
    }

    /**
     * 返回放置的索引值，每次排序，取首个元素作为基准，小的放左边，大的放右边
     * @param arr 待排序数组
     * @param lo 左边界
     * @param hi 右边界
     * @return 用于每一小组排序的元素放置的索引
     */
    public static int partition(int[][] arr, int lo, int hi){
        //需要两个指针，一个指向lo，一个指向hi+1
        int left = lo;
        int right = hi+1;
        int[] temp = arr[lo];
        while (true){
            //先从右往左扫描,如果大于temp就继续
            while(less(temp,arr[--right])){
                if(right == lo){
                    break;
                }
            }
            while(less(arr[++left],temp)){
                if(left == hi){
                    break;
                }
            }
            if(right <= left){
                break;
            }else{
                exch(arr,left,right);
            }

        }
        exch(arr,lo,right);
        return right;
    }

    /**
     * 比较两个区间的大小，左边界相等则比较右边界
     * @param arr1 区间1
     * @param arr2 区间2
     * @return arr1小于arr2返回true，否则返回false
     */
    public static boolean less(int[] arr1, int[] arr2){
        if(arr1[0] == arr2[0]){
            return arr1[1]-arr2[1] < 0;
        }
        return arr1[0]-arr2[0] < 0;
    }

    /**
     * 交换两个区间
     * @param arr 二维数组
     * @param i 第i个区间
     * @param j 第j个区间
     */
    public static void exch(int[][] arr, int i, int j){
        int[] temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
